//超时
// class LRUCache {
// public:
//     LRUCache(int capacity)
//     : _capacity(capacity)
//     {}
    
//     int get(int key) {
//         if (_kv.count(key))
//         {
//             _l.remove(key);
//             _l.push_back(key);
//             return _kv[key];
//         }
//         return -1;
//     }
    
//     void put(int key, int value) {
//         if (_kv.count(key))
//         {
//             _l.remove(key);
            
//         }
//         else if (_kv.size() >= _capacity)
//         {
//             int key = _l.front();
//             if (_kv.count(key))
//                 _kv.erase(key);
//             _l.pop_front();
//         }
            

//             _kv[key] = value;
//             _l.push_back(key);
        
//     }
// private:
//     int _capacity;
//     unordered_map<int, int> _kv;
//     list<int> _l;
// };

//维护一个双链表和map
//双链表的节点存储的是k_v结构，链表头存放的是最新的数据，链表尾是最旧的数据
//map存放的是每个key对应到的链表节点的地址

class LRUCache {
    struct ListNode
    {
        ListNode* _prev;
        ListNode* _next;
        pair<int, int> _kv;

        ListNode(pair<int, int> kv, ListNode* prev = nullptr, ListNode* next = nullptr)
        : _kv(kv), _prev(prev), _next(next)
        {}

    };
    class List
    {
    public:
        List()
        : _length(0)
        {
            _dummyHead = new ListNode(make_pair(0, 0));
            _dummyTail = new ListNode(make_pair(0, 0));

            _dummyHead->_next = _dummyTail;
            _dummyTail->_prev = _dummyHead;
        }

        void push_front(ListNode* newNode)
        {
            ListNode* headNext = _dummyHead->_next;
            _dummyHead->_next = newNode;
            newNode->_prev = _dummyHead;
            newNode->_next = headNext;
            headNext->_prev = newNode;

            _length++;
        }

        ListNode* pop_back()
        {
            ListNode* popNode = _dummyTail->_prev;
            popNode->_prev->_next = _dummyTail;
            _dummyTail->_prev = popNode->_prev;

            return popNode;
        }

        ListNode* erase(ListNode* node)
        {
            ListNode* n_prev = node->_prev;
            ListNode* n_next = node->_next;

            n_prev->_next = n_next;
            n_next->_prev = n_prev;

            _length--;

            return node;
        }

    private:
        int _length;
        ListNode* _dummyHead;
        ListNode* _dummyTail;
    };
public:
    LRUCache(int capacity)
    : _capacity(capacity)
    {}
    
    //如果key不在map中，返回-1
    //如果key在map中
    //  提取key所对应的链表节点，将其从链表中删除，并放到链表头
    //  返回value
    int get(int key) {
        if (!_hash.count(key))
            return -1;
        
        ListNode* node = _hash[key];
        _list.push_front(_list.erase(node));
        return node->_kv.second;
    }
    
    //如果key不在map中
    //  如果map.size() < capacity，直接在链表头插入，并更新map
    //  否则，删除链表尾的节点，再在链表头插入，更新map
    //如果key在map中
    //  提取key所对应的链表节点，将其从链表中删除，并放到链表头，同时更新value
    void put(int key, int value) {
        if (!_hash.count(key))
        {
            if (_hash.size() >= _capacity)
            {
                ListNode* Node = _list.pop_back();
                _hash.erase(Node->_kv.first);

                delete Node;
            }
            
            ListNode* newNode = new ListNode(make_pair(key, value));

            _list.push_front(newNode);
            _hash.insert(make_pair(key, newNode));
        }
        else
        {
            ListNode* node = _hash[key];
            node->_kv = make_pair(key, value);
            _list.push_front(_list.erase(node));
        }
    }
private:
    int _capacity;
    unordered_map<int, ListNode*> _hash;
    List _list;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */